106. Construct Binary Tree from Inorder and Postorder Traversal
Medium

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

 

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

 

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder and postorder consist of unique values.
  • Each value of postorder also appears in inorder.
  • inorder is guaranteed to be the inorder traversal of the tree.
  • postorder is guaranteed to be the postorder traversal of the tree.
Accepted
305,239
Submissions
598,646
Seen this question in a real interview before?
Companies

Average Rating: 4.71 (63 votes)

Premium

Solution


How to traverse the tree

There are two general strategies to traverse a tree:

  • Depth First Search (DFS)

    In this strategy, we adopt the depth as the priority, so that one would start from a root and reach all the way down to certain leaf, and then back to root to reach another branch.

    The DFS strategy can further be distinguished as preorder, inorder, and postorder depending on the relative order among the root node, left node and right node.

  • Breadth First Search (BFS)

    We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.

On the following figure the nodes are enumerated in the order you visit them, please follow 1-2-3-4-5 to compare different strategies.

postorder

In this problem one deals with inorder and postorder traversals.




Approach 1: Recursion

How to construct the tree from two traversals: inorder and preorder/postorder/etc

Problems like this one are often at Facebook interviews, and could be solved in O(N)\mathcal{O}(N) time:

  • Start from not inorder traversal, usually it's preorder or postorder one, and use the traversal picture above to define the strategy to pick the nodes. For example, for preorder traversal the first value is a root, then its left child, then its right child, etc. For postorder traversal the last value is a root, then its right child, then its left child, etc.

  • The value picked from preorder/postorder traversal splits the inorder traversal into left and right subtrees. The only information one needs from inorder - if the current subtree is empty (= return None) or not (= continue to construct the subtree).

bla

Algorithm

  • Build hashmap value -> its index for inorder traversal.

  • Return helper function which takes as the arguments the left and right boundaries for the current subtree in the inorder traversal. These boundaries are used only to check if the subtree is empty or not. Here is how it works helper(in_left = 0, in_right = n - 1):

    • If in_left > in_right, the subtree is empty, return None.

    • Pick the last element in postorder traversal as a root.

    • Root value has index index in the inorder traversal, elements from in_left to index - 1 belong to the left subtree, and elements from index + 1 to in_right belong to the right subtree.

    • Following the postorder logic, proceed recursively first to construct the right subtree helper(index + 1, in_right) and then to construct the left subtree helper(in_left, index - 1).

    • Return root.

Implementation

Current
1 / 7

Complexity Analysis

  • Time complexity : O(N)\mathcal{O}(N). Let's compute the solution with the help of master theorem T(N)=aT(bN)+Θ(Nd)T(N) = aT\left(\frac{b}{N}\right) + \Theta(N^d). The equation represents dividing the problem up into aa subproblems of size Nb\frac{N}{b} in Θ(Nd)\Theta(N^d) time. Here one divides the problem in two subproblemes a = 2, the size of each subproblem (to compute left and right subtree) is a half of initial problem b = 2, and all this happens in a constant time d = 0. That means that logb(a)>d\log_b(a) > d and hence we're dealing with case 1 that means O(Nlogb(a))=O(N)\mathcal{O}(N^{\log_b(a)}) = \mathcal{O}(N) time complexity.

  • Space complexity : O(N)\mathcal{O}(N), since we store the entire tree.

Report Article Issue

Comments: 20
SoumavaBan's avatar
Read More

What is the reason that we have to construct the right sub-tree first and then the left sub-tree?

40
Show 9 replies
Reply
Share
Report
cxhcxh's avatar
Read More

[Java] Recursive | Easy to understand

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0 || postorder.length == 0) return null;
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        if(postorder.length == 1) return root;

        int index = 0;
        for(int val : inorder){
            if(val == root.val) break;
            index++;
        }

        root.left = buildTree(Arrays.copyOfRange(inorder, 0, index), Arrays.copyOfRange(postorder, 0, index));
        root.right = buildTree(Arrays.copyOfRange(inorder, index + 1, inorder.length), Arrays.copyOfRange(postorder, index, postorder.length - 1));

        return root;
    }

10
Show 3 replies
Reply
Share
Report
lenchen1112's avatar
Read More

Refer to the greate answer of @StefanPochmann in this post.
It's possible to reach O(N) time without the index map.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def build(bound = None):
            if not inorder or inorder[-1] == bound: return None
            root = TreeNode(postorder.pop())
            root.right = build(root.val)
            inorder.pop()
            root.left = build(bound)
            return root

        return build()

10
Show 3 replies
Reply
Share
Report
FCookie's avatar
Read More

Since we are popping nodes from the end from post-order list, we come across nodes in the order: node, node.right and then node.left

7
Reply
Share
Report
LeanderLXZ's avatar
Read More

A very simple Python implementation.

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
    if not inorder:
        return None
    cur_val = postorder.pop()
    idx = inorder.index(cur_val)
    right = self.buildTree(inorder[idx+1:], postorder)
    left = self.buildTree(inorder[:idx], postorder)
    return TreeNode(cur_val, left, right)

5
Show 1 reply
Reply
Share
Report
antolenin's avatar
Read More

My js solution

var splitArray = (arr, splitter) => {
    const index = arr.indexOf(splitter);
    const left = arr.slice(0, index);
    const right = arr.slice(index + 1);
    
    return { left, right };
}

var buildTree = function(inorder, postorder) {
    if (!inorder.length) {
        return null;
    }
    
    const current = postorder.pop();
    const isLeaf = inorder.length === 1;
    
    if (isLeaf) {
        return {
            val: current,
            left: null,
            right: null,
        }
    }
    
    const splitted = splitArray(inorder, current);
    
    return {
        val: current,
        right: buildTree(splitted.right, postorder),
        left: buildTree(splitted.left, postorder),
    }
};

5
Show 1 reply
Reply
Share
Report
drbn's avatar
Read More

var buildTree = function(inorder, postorder) {
    if (inorder.length === 0) return null;
    if (inorder.length === 1) return new TreeNode(inorder[0]);

    const rootVal = postorder.pop();
    const leftInOrder = inorder.slice(0, inorder.indexOf(rootVal));
    const rightInOrder = inorder.slice(inorder.indexOf(rootVal)+1, inorder.length);
    
    const leftPostOrder = postorder.slice(0, leftInOrder.length);
    const rightPostOrder = postorder.slice(leftInOrder.length, postorder.length);

    const leftTreeNode = buildTree(leftInOrder, leftPostOrder);
    const rightTreeNode = buildTree(rightInOrder, rightPostOrder);
    
    return new TreeNode(rootVal, leftTreeNode, rightTreeNode);
};

4
Reply
Share
Report
danloringess's avatar
Read More

Why is the size of each subproblem half the size of the initial problem? If you have a very unbalanced graph you can have two subproblems one of size 999999 (N-1) and the other with size 1, in that case isn't b very close to 1 and not 2?

2
Show 1 reply
Reply
Share
Report
constantinpojoga's avatar
Read More

JS recursive solution:

var buildTree = function(inorder, postorder) {
  if (!postorder.length) return null;
    
  if (postorder.length === 1) {
    return new TreeNode(postorder[0])
  } else {
    const val = postorder.pop();
    const idx = inorder.indexOf(val);
    
    return new TreeNode(
      val, 
      buildTree(inorder.slice(0, idx), postorder.slice(0, idx)),    
      buildTree(inorder.slice(idx + 1), postorder.slice(idx)),
    )
  }
};

1
Reply
Share
Report
Mo_Kiani's avatar
Read More

I've managed to solve the problem with iteration and a stack. I've been trying really hard to prove why this solution works, but I'm having trouble solidly articulating it. If anyone knows how to put into words why this solution works I'd really appreciate the help.

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not postorder:
            return None
        postIter = reversed(postorder)
        root = TreeNode(next(postIter))
        parentStack = [root]
        
        i = len(inorder) - 1
        for val in postIter:
            node = TreeNode(val)
            if inorder[i] == parentStack[-1].val:
                i -= 1
                parent = parentStack.pop()
                
                while parentStack and inorder[i] == parentStack[-1].val:
                    parent = parentStack.pop()
                    i -= 1
                
                parent.left = node
                parentStack.append(node)
                
            else:    
                parentStack[-1].right = node
                parentStack.append(node)

        return root        

1
Reply
Share
Report
Success
Details
Runtime: 16 ms, faster than 79.85% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
Memory Usage: 26.6 MB, less than 16.12% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.
Time Submitted
Status
Runtime
Memory
Language
06/17/2021 08:30Accepted16 ms26.6 MBcpp
05/18/2021 19:19Accepted28 ms26 MBcpp
05/18/2021 19:14Accepted24 ms26 MBcpp
07/27/2020 12:43Accepted8 ms23.9 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.